#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode
{
  ElemType data;
  struct LinkNode *next;
} LinkNode;
typedef struct
{
  LinkNode *front, *rear; // 声明队列的头指针和尾指针
} LinkQueue;

// 初始化链式队列(带头结点版本)
void InitQueue(LinkQueue &q)
{
  q.front = q.rear = (LinkNode *)malloc(sizeof(LinkNode));
  q.front->next = NULL;
  // 不带头结点的版本
  // q.front = q.rear = NULL;
}

// 入队(带头结点的)
void EnQueue(LinkQueue &q, ElemType e)
{
  LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
  s->data = e;
  s->next = NULL;   // 都是在队尾插入的 所以后面的都指向null
  q.rear->next = s; // 新节点插入到rear之后
  q.rear = s;       // 让队尾结点指向新插入的结点
}

// 出队(带头结点)
bool DeQueue(LinkQueue &q, ElemType &e)
{
  if (q.front == q.rear)
    return false;
  LinkNode *p = q.front->next;
  x = p->data;
  q.front->next = p->next;
  if (q.rear == p) // 此时最后一个结点出队
  {
    q.rear = q.front;
  }
  free(p);
  return true;
}

// 入队(不带头结点的)
void EnQueueNoHead(LinkQueue &q, ElemType e)
{
  LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
  s->data = e;
  s->next = NULL;      // 都是在队尾插入的 所以后面的都指向null
  if (q.front == NULL) // 第一次有数据插入时，把front 和 rear 指针都指向它
  {
    q.front = s;
    q.rear = s;
  }
  else
  {
    q.rear->next = s;
    q.rear = s;
  }
}

// 出队(不带头结点的)
bool DeQueueNoHead(LinkQueue &q, ElemType e)
{
  if (q.front == NULL)
    return false;
  LinkNode *p = q.front; // 出队的结点
  e = p->data;
  q.front = p->next;
  if (q.front == q.rear) // 最后一个结点出队
  {
    q.front = q.rear = NULL;
  }
  free(p);
  return true;
}

// 获取队头元素
void getTop(LinkQueue q, ElemType &e)
{
  // 带头结点的
  e = q.front->next->data;
  // 不带头结点的
  // e = q.front->data;
}

// 判空
bool IsEmpty(LinkQueue q)
{
  return q.front == q.rear;
  // or q.front == NULL;
}

int main()
{
  LinkQueue Q;
  InitQueue(Q);
}